package a11_单调栈;

import java.util.Arrays;
import java.util.Stack;

/**
 * <p>
 * a05_柱状图中最大的矩形
 * </p>
 *
 * @author flyduck
 * @since 2025/3/7
 */
public class a05_柱状图中最大的矩形 {
    //以某个点为基准，假设左边没有比这个矮的，那么就可以贯穿左边
    //以某个点为基准，假设右边有比这个矮的，那么就可以贯穿右边矮的之前


    //单调栈：栈口最大

    //首尾特殊处理：头部和尾部加0
    //如果数组是2,4,6,8
    //如果数组是8,6,4,2

    public static void main(String[] args) {
        a05_柱状图中最大的矩形 test = new a05_柱状图中最大的矩形();
        test.largestRectangleArea(new int[]{2,4,6,8});
    }
    public int largestRectangleArea(int[] oldNums) {
        int[] nums = new int[oldNums.length+2];
        System.arraycopy(oldNums,0,nums,1,oldNums.length);

        int result = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        for (int i = 1; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]){
                Integer pop = stack.pop();
                if(!stack.isEmpty()){
                   int height = nums[pop];
                   int width = i - stack.peek() - 1;
                   result = Math.max(result, height * width);
                }
            }
            stack.push(i);
        }

        return result;
    }
}
